﻿//面试题 01.01.判断字符是否唯一
class Solution {
public:
    bool isUnique(string astr) {
        int n = astr.size();
        if (n > 26) return false;

        int ret = 0;
        for (int i = 0; i < n; i++)
        {
            int pos = astr[i] - 'a';
            if (((ret >> pos) & 1) == 0)
            {
                ret |= (1 << pos);
            }
            else
            {
                return false;
            }
        }
        return true;
    }
};

//268.丢失的数字
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ret = nums.size();
        for (int i = 0; i < nums.size(); i++)
        {
            ret ^= nums[i];
            ret ^= i;
        }
        return ret;
    }
};

//371.两整数之和
class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0)
        {
            int sum = a ^ b;
            int carry = (a & b) << 1;
            a = sum;
            b = carry;
        }
        return a;
    }
};

//174.地下城游戏
class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon)
    {
        int row = dungeon.size(), col = dungeon[0].size();
        vector<vector<int>> dp(row + 1, vector<int>(col + 1, INT_MAX));
        dp[row - 1][col] = dp[row][col - 1] = 1;

        for (int i = row - 1; i >= 0; i--)
        {
            for (int j = col - 1; j >= 0; j--)
            {
                dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = max(1, dp[i][j]);
            }
        }

        return dp[0][0];
    }
};